Paul Keres sinh ngày 7 tháng 1 năm 1916 tại Narva, Estonia, khu vực khi đó đang được đặt dưới sự cai quản của Đế quốc Nga. Keres lần đầu biết đến cờ vua qua cha và người em trai Harald. Do sự khan hiếm tài liệu về cờ vua tại thành phố nhỏ nơi mình sinh sống, Keres đã tìm hiểu các ký hiệu cờ vua từ những câu đố cờ vua trên tờ nhật báo và biên soạn được một bộ sưu tập hơn 1000 ván đấu viết tay.[2] Trong thời kỳ đầu, Keres được biết đến với phong cách tấn công rõ nét và xuất sắc.[3]

Keres từng ba lần vô địch các giải cờ vua lứa tuổi học sinh Estonia vào các năm 1930, 1932 và 1933. Trình độ của Keres dần nâng cao sau các ván cờ thư tín, hình thức được ông sử dụng rộng rãi thời trung học. Ông đã chơi khoảng 500 ván kiểu này, có giai đoạn chơi đồng thời 150 ván. Vào năm 1935 Keres giành chức vô địch giải cờ thư tín quốc tế Internationaler Fernschachbund. Từ năm 1937 đến năm 1941 ông học toán tại trường đại học Tartu và ganh đua trong một số trận đấu diễn ra giữa các trường đại học.[4]